/*
 * BinaryTree.h
 *
 *  Created on: Oct 28, 2010
 *      Author: Jacob
 */

#ifndef BINARYTREE_H_
#define BINARYTREE_H_
#include "Node.h"
#include <string.h>
#include <sstream>
using std::string;
using std::ostringstream;
using std::stringstream;
using std::string;
//REMOVE ME
#include <iostream>
using std::cout;

template<typename T>
class BinaryTree
{
public:
	static BinaryTree<T>* newTree();
	bool isFull();
	bool isEmpty();
	bool insert(Node<T>* nodeToBeInserted);
	bool insert(T data);
	int getNumberOfNodes();
	Node<T>* retrieveNode(Node<T>* nodeToBeFound);
	Node<T>* retrieveNode(T nodesValue);
	bool deleteNode(Node<T>* nodeToBeRemoved);
	bool deleteNode(T nodesValue);
	void clearTree();
	string preorderTraversal();
	string postorderTraversal();
	string inorderTraversal();
	Node<T>* first();
	Node<T>* last();
	string getSaveFileData();
	virtual ~BinaryTree();
private:
	int numberOfNodes;
	Node<T>* root;
	Node<T>* searchResult;
	string lineBreak;
	ostringstream preOrderStream, postOrderStream, inOrderStream;
	Node<T>* constructNodeFromT(T data);
	Node<T>* search(Node<T>* &rootNode, Node<T>* &nodeToBeFound);
	bool insertNode(Node<T>* &rootNode, Node<T>* nodeToBeInserted,
			Node<T>* parent);
	void preorder(Node<T>* &node);
	void postorder(Node<T>* &node);
	void inorder(Node<T>* &node);
	void destructTree(Node<T>* &node);
	bool isNodeLeaf(Node<T>* node);
	int getNumberOfNodesChildren(Node<T>* node);
	void detatchNodeFromParent(Node<T>* &child);
	bool deleteNodeWithOneChild(Node<T>* node);
	bool deleteNodeWithTwoChildren(Node<T>* node);
	bool deleteNodeWithNoChildren(Node<T>* node);
	bool deletePreparedNode(Node<T>* node);
	BinaryTree();
};

/*
 * Factory pattern for creating a tree.
 */
template<typename T>
BinaryTree<T>* BinaryTree<T>::newTree()
{
	return new BinaryTree<T> ();
}

template<typename T>
BinaryTree<T>::BinaryTree()
	:numberOfNodes(0), root(NULL)
{
	numberOfNodes = 0;
	lineBreak = "\n=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n";
}

template<typename T>
BinaryTree<T>::~BinaryTree()
{
	destructTree(root);
}

/*
 * Perform an post order traversal, to delete
 * the tree from the bottom up. Function should be given the root node
 * to perorm deletion on.
 */
template<typename T>
void BinaryTree<T>::destructTree(Node<T>* &node)
{
	if (node == NULL)
		return;
	else if (node != NULL)
	{
		destructTree(node->left);
		destructTree(node->right);
		node->parent = NULL;
		delete node;
		--numberOfNodes;
	}
}

template<typename T>
bool BinaryTree<T>::isEmpty()
{
	if( this->numberOfNodes > 0)
		return false;
	else
		return true;

}

/*
 * Constructs a node from T and attempts to insert it into the tree
 * returns the result of insertion
 */
template<typename T>
bool BinaryTree<T>::insert(T data)
{
	Node<T>* nodeToBeInserted = constructNodeFromT(data);
	return insertNode(root, nodeToBeInserted, NULL);
}

/*
 * Takes a node, and calls the insert function
 */
template<typename T>
bool BinaryTree<T>::insert(Node<T>* nodeToBeInserted)
{
	return insertNode(root, nodeToBeInserted, NULL);
}

/*
 * Recursive mehtod for inserting a node into the tree.
 */
template<typename T>
bool BinaryTree<T>::insertNode(Node<T>* &rootNode, Node<T>* nodeToBeInserted,
		Node<T>* parent)
{
	if (rootNode == NULL)
	{
		//If recursion gets here, the node to be inserted is where we want it, so insert.
		rootNode = nodeToBeInserted;
		rootNode->parent = parent;
		++numberOfNodes;
		return true;
	}
	//shoot lesser to left
	else if (nodeToBeInserted->getData() < rootNode->getData())
	{
		insertNode(rootNode->left, nodeToBeInserted, rootNode);
		return true;
	}
	//shoot greater to right.
	else if (nodeToBeInserted->getData() > rootNode->getData())
	{
		insertNode(rootNode->right, nodeToBeInserted, rootNode);
		return true;
	}
	else if (nodeToBeInserted->getData() == rootNode->getData())
	{
		//node exists in tree, so we cannot take this node. return false
		return false;
	}

	return true;
}

/*
 * Calls, and returns the result of the search function
 */
template<typename T>
Node<T>* BinaryTree<T>::retrieveNode(Node<T>* nodeToBeFound)
{
	if (nodeToBeFound == NULL)
		return NULL;

	return search(root, nodeToBeFound);
}

/*
 * Recursive search function which takes a node, and searches for the
 * node in the tree. Returns whether the node was found.
 */
template<typename T>
Node<T>* BinaryTree<T>::search(Node<T>* &rootNode, Node<T>* &nodeToBeFound)
{
	//stops recursion
	if (rootNode == NULL)
		return NULL;

	//search left2089190
	else if (nodeToBeFound->getData() < rootNode->getData())
	{
		return search(rootNode->left, nodeToBeFound);
	}
	//search right
	else if (nodeToBeFound->getData() > rootNode->getData())
	{
		return search(rootNode->right, nodeToBeFound);
	}
	//if recursion got here, then its in ze tree!
	if (nodeToBeFound == rootNode)
		return nodeToBeFound;

	//aw value not found :(
	return NULL;
}

/*
 * Takes a templated value, and searches the tree
 * for a node containing that value
 */
template<typename T>
Node<T>* BinaryTree<T>::retrieveNode(T nodesValue)
{
	//non recursive version

	searchResult = root;

	while (searchResult != NULL)
	{
		//we have found the node
		if (searchResult->getData() == nodesValue)
			return searchResult;
		//Maintain BSP, and search left for node.
		else if (searchResult->getData() > nodesValue)
			searchResult = searchResult->left;
		//Maintain BSP and search right for node.
		else if (searchResult->getData() < nodesValue)
			searchResult = searchResult->right;
	}

	return NULL;
}

/*
 * Takes a templated value, calls the search function
 * to get a ptr to the node in the tree. Attempts to delete
 * that node and returns the result.
 */
template<typename T>
bool BinaryTree<T>::deleteNode(T nodesValue)
{
	Node<T>* node = retrieveNode(nodesValue);
	if (node == NULL)
		return false;
	else
		return deleteNode(node);
}

/*
 * Determines which deletion method to use based
 * on the number of children that node has,
 * and if it is a leaf node. returns wether the
 * value could be found and deleted.
 */
template<typename T>
bool BinaryTree<T>::deleteNode(Node<T>* nodeToBeDeleted)
{
	//node not found
	if (nodeToBeDeleted == NULL)
		return false;

	//delete a leaf node.
	if (isNodeLeaf(nodeToBeDeleted))
	{
		return deleteNodeWithNoChildren(nodeToBeDeleted);
	}
	else
	{
		//delete node with one child
		if (getNumberOfNodesChildren(nodeToBeDeleted) == 1)
		{
			return deleteNodeWithOneChild(nodeToBeDeleted);
		}
		//delete node with two children
		else if (getNumberOfNodesChildren(nodeToBeDeleted) == 2)
		{
			return deleteNodeWithTwoChildren(nodeToBeDeleted);
		}
	}

	return false;
}

/*
 * Method for deleting a node with only one child
 */
template<typename T>
bool BinaryTree<T>::deleteNodeWithNoChildren(Node<T>* node)
{
	//free node from parents and delete.
	detatchNodeFromParent(node);
	return deletePreparedNode(node);
}

/*
 * Method for deleting a node that has one child.
 */
template<typename T>
bool BinaryTree<T>::deleteNodeWithOneChild(Node<T>* node)
{
	Node<T>* nodesParent = node->parent;
	Node<T>* nodesChild;

	//find if node is it's parents left or right
	if (node->left != NULL)
		nodesChild = node->left;
	else if (node->right != NULL)
		nodesChild = node->right;

	//delete node and replace node's parents reference to itself, with  node's child.
	if (nodesParent->left == node)
	{
		nodesParent->left = nodesChild;
		nodesChild->parent = nodesParent;
	}
	else
	{
		nodesParent->right = nodesChild;
		nodesChild->parent = nodesParent;
	}

	//remove the node, decrement size
	return deletePreparedNode(node);
}

/*
 * Case for deleting a node that has two children. returns true or false
 * depending on if the deletion was successful
 */
template<typename T>
bool BinaryTree<T>::deleteNodeWithTwoChildren(Node<T>* node)
{
	Node<T>* smallestInRightSubtree = node->left;

	//find smallest node in right subtree (left most)
	while (smallestInRightSubtree->left != NULL)
	{
		smallestInRightSubtree = smallestInRightSubtree->left;
	}

	//swap values with node to be deleted.
	T smallestInRightsValue = smallestInRightSubtree->getData();
	node->setData(smallestInRightsValue);

	//delete smallest in right subtree as it only has one child.
	return deleteNode(smallestInRightSubtree);
}

/*
 * Takes a node, and decrements the running total, then deletes that node.
 */
template<typename T>
bool BinaryTree<T>::deletePreparedNode(Node<T>* node)
{
	--numberOfNodes;
	delete node;
	return true;
}

/*
 * If the node has no assigned left or right node, it is a leaf node.
 */
template<typename T>
bool BinaryTree<T>::isNodeLeaf(Node<T>* node)
{
	//if node has no children it is a leaf node, return true.
	if (node->left == NULL && node->right == NULL)
		return true;
	else
		return false;
}

/*
 * Takes a node and counts how many assigned pointers it has
 * to other nodes. This is used to determine which deletion case
 * to use
 */
template<typename T>
int BinaryTree<T>::getNumberOfNodesChildren(Node<T>* node)
{
	//count the number of children and return

	if (node->left != NULL && node->right != NULL)
		return 2;
	else if (!((node->left == NULL) && (node->right == NULL)))
		return 1;
	else
		return 0;
}

/*
 * When deleting a node, we must first remove the reference the nodes parents
 * have of it.
 */
template<typename T>
void BinaryTree<T>::detatchNodeFromParent(Node<T>* &child)
{
	//remove node's parent's reference to it.

	if (child->parent->left == child)
		child->parent->left = NULL;
	else
		child->parent->right = NULL;
}

/*
 * Removes all data contained in the tree
 */
template<typename T>
void BinaryTree<T>::clearTree()
{
	this->destructTree(root);
}

/*
 * Returns the running total of nodes in the tree
 */
template<typename T>
int BinaryTree<T>::getNumberOfNodes()
{
	return this->numberOfNodes;
}

/*
 * Takes a value and constructs a templated node, which gets returned
 */
template<typename T>
Node<T>* BinaryTree<T>::constructNodeFromT(T data)
{
	Node<T>* nodeToBeReturned = Node<T>::newNodeFromData(data);
	return nodeToBeReturned;
}

template<typename T>
string BinaryTree<T>::preorderTraversal()
{
	preOrderStream.clear();
	cout << lineBreak << "Preorder Traversal" << lineBreak;
	preorder(root);
	return preOrderStream.str();
}

/*
 * Performs a preorder traversal on the tree
 */
template<typename T>
void BinaryTree<T>::preorder(Node<T>* &node)
{
	preOrderStream << node->getData() << "\n";/* << " PTR: " << node << " Parent: " << node->parent*/

	if (node->left != NULL)
		preorder(node->left);
	if (node->right != NULL)
		preorder(node->right);
}

template<typename T>
string BinaryTree<T>::postorderTraversal()
{
	cout << lineBreak << "Postorder Traversal" << lineBreak;
	postorder(root);
	return postOrderStream.str() + lineBreak;
}

/*
 * Performs a post order traversal on the tree
 */
template<typename T>
void BinaryTree<T>::postorder(Node<T>* &node)
{
	postOrderStream.clear();
	if (node->left != NULL)
		postorder(node->left);
	if (node->right != NULL)
		postorder(node->right);
	postOrderStream << node->getData() << "\n";
}

template<typename T>
string BinaryTree<T>::inorderTraversal()
{
	inOrderStream.clear();
	cout << lineBreak << "Inorder Traversal" << lineBreak;
	inorder(root);
	return inOrderStream.str() + lineBreak;
}

/*
 * Performs a inorder traversal on tree.
 */
template<typename T>
void BinaryTree<T>::inorder(Node<T>* &node)
{
	if (node->left != NULL)
		inorder(node->left);
	inOrderStream << node->getData() << "\n";
	if (node->right != NULL)
		inorder(node->right);
}

template<typename T>
string BinaryTree<T>::getSaveFileData()
{
//	saveFileStream << node->getData() << "\n";
//	if (node->left != NULL)
//		preorder(node->left);
//	if (node->right != NULL)
//		preorder(node->right);
}

/*
 * Returns the lowest value contained in the tree
 */
template<typename T>
Node<T>* BinaryTree<T>::first()
{
	Node<T>* current = root;

	while (current->left != NULL)
	{
		current = current->left;
	}

	return current;
}

/*
 * Returns the maximum value contained in the tree
 */
template<typename T>
Node<T>* BinaryTree<T>::last()
{
	Node<T>* current = root;

	while (current->right != NULL)
	{
		current = current->right;
	}

	return current;
}

#endif /* BINARYTREE_H_ */
